/*
Please write a function in Java to tell if string A is a substring of another string B
without using String.indexOf(), String.lastIndexOf() or String.contains(). Please figure
out the time complexity of the algorithm you write.

Data: 2017.04.22

**/

#include<iostream>
#include<string>

using namespace std;

//O(m * n)
bool IsSubstringDirect(string a, string b){

    int i = 0;
    while( i+b.size() <= a.size() ){

        bool flag = true;
        for(int j=0; j<b.size(); j++){
            if(a[i+j] != b[j]){
                flag = false;
            }
        }

        if(flag)
            return true;
        i++;
    }
    return false;
}


int IsSubstringDirect2(string s, string p){

    int sLen = s.size();
    int pLen = p.size();

    int i = 0;
    int j = 0;
    while (i < sLen && j < pLen)
    {
        if (s[i] == p[j])
        {
            //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
            i++;
            j++;
        }
        else
        {
            //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
            i = i - j + 1;
            j = 0;
        }
    }
    //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
    if (j == pLen)
        return i - j;
    else
        return -1;
}


bool GetNext(string p, int next[]){

    int pLen = p.size();
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        //p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

//http://blog.csdn.net/v_july_v/article/details/7041827
//O(m + n)
int IsSubstringKMP(string s, string p){

    int i = 0;
    int j = 0;
    int sLen = s.size();
    int pLen = p.size();

    int next[pLen];
    GetNext(p, next);

    while (i < sLen && j < pLen)
    {
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
        if (j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
            //next[j]即为j所对应的next值
            j = next[j];
        }
    }
    if (j == pLen)
        return i - j;
    else
        return -1;
}






int main(int argc, char *argv[])
{
    string a = "hello world";
    string b = "llo";
    string c = "ld";

    cout << IsSubstringDirect2(a, b) << endl;
    cout << IsSubstringDirect2(a, c) << endl;

    cout << IsSubstringKMP(a, b) << endl;
    cout << IsSubstringKMP(a, c) << endl;

    return 0;
}
